// Package _1_给定二叉树求祖宗数组 main
// @Title _1_给定二叉树求祖宗数组
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-16 15:14
// @Create  2022-01-16 15:14
package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 给定二叉树中的一个节点和根节点，返回他对应的祖宗数组
func findFatherSet(root, p *TreeNode) []int {
	if root == nil || p == nil {
		return nil
	}
	var ans []int
	fatherMap := make(map[*TreeNode]*TreeNode)
	fatherMap[root] = root
	process(root, fatherMap)
	//for k,v := range fatherMap{
	//	if k != nil{
	//		fmt.Println(k.Val,v.Val)
	//	}
	//
	//}
	hashSet := make(map[*TreeNode]*TreeNode)
	cur := p
	for cur != fatherMap[cur] {
		if _, ok := hashSet[cur]; !ok {
			hashSet[cur] = cur
			ans = append(ans, cur.Val)
		}
		cur = fatherMap[cur]
	}
	hashSet[cur] = root
	ans = append(ans, root.Val)
	return ans
}

func process(root *TreeNode, fatherMap map[*TreeNode]*TreeNode) {
	if root == nil {
		return
	}
	fatherMap[root.Left] = root
	fatherMap[root.Right] = root
	process(root.Left, fatherMap)
	process(root.Right, fatherMap)
}
func main() {
	temp := TreeNode{
		8, nil, nil,
	}
	root := TreeNode{
		1,
		&TreeNode{
			2,
			&TreeNode{
				4,
				&temp,
				nil,
			},
			&TreeNode{
				5,
				nil,
				nil,
			},
		},
		&TreeNode{
			3,
			&TreeNode{
				6,
				nil,
				nil,
			},
			&TreeNode{
				7,
				nil,
				nil,
			},
		},
	}
	fmt.Println(findFatherSet(&root, &temp))
}
